#Copyright (c) 2020 Ocado. All Rights Reserved.

import vptree, itertools
import numpy as np


class _ExtendedVPTree(vptree.VPTree):
    """
    VPTree class extended to include the list of points within the tree
    VPTree类扩展为包含树中的点 列表
    _ExtendedVPTree 是一个 Python 类，继承自 vptree.VPTree，它对 vptree.VPTree 类进行了扩展
    需要注意的是，_ExtendedVPTree 类是 vptree 库的一个私有类，所以在使用时需要小心，确保正确使用和理解。
    好像就是 在自带vptree的基础上，加了一个函数和几个属性
    """
    def __init__(self, points, dist_fn):
        """
        :param points: List of points to add to the vp-tree
        :param dist_fn: Metric distance function
        ：param points：要添加到vp树的点列表
        ：param dist_fn：公制距离函数
        """
        super().__init__(points, dist_fn)
        #super()用来调用父类(基类)的方法，__init__()是类的构造方法
        self.points = points
        self.size = len(points)

    def get_n_nearest_neighbors(self, query, n_neighbors):
        """
        Override parent method to use <= when finding nearest neighbours to ensure a neighbour is returned even at infinite/nan distance
        重写父类的方法，使用“<=”来寻找最近邻居，以确保在无限/NaN距离时也返回一个邻居。
        """
        if not isinstance(n_neighbors, int) or n_neighbors < 1:
            raise ValueError('n_neighbors must be strictly positive integer')
        neighbors = vptree._AutoSortingList(max_size=n_neighbors)
        nodes_to_visit = [(self, 0)]
        furthest_d = np.inf
        while len(nodes_to_visit) > 0:
            node, d0 = nodes_to_visit.pop(0)
            if node is None or d0 > furthest_d:
                continue
            d = self.dist_fn(query, node.vp)
            if d <= furthest_d:     #Replaced < with <=
                neighbors.append((d, node.vp))
                furthest_d, _ = neighbors[-1]
            if node._is_leaf():
                continue
            if node.left_min <= d <= node.left_max:
                nodes_to_visit.insert(0, (node.left, 0))
            elif node.left_min - furthest_d <= d <= node.left_max + furthest_d:
                nodes_to_visit.append((node.left,
                                       node.left_min - d if d < node.left_min
                                       else d - node.left_max))
            if node.right_min <= d <= node.right_max:
                nodes_to_visit.insert(0, (node.right, 0))
            elif node.right_min - furthest_d <= d <= node.right_max + furthest_d:
                nodes_to_visit.append((node.right,
                                       node.right_min - d if d < node.right_min
                                       else d - node.right_max))
        if len(neighbors) == 0:
            neighbors = [(np.nan, point) for point in self.points[:n_neighbors]] #Return any point(s) if query contains np.nan
        return list(neighbors)


class DynamicVPTree:
    """
    Dynamic vp-tree implemented using index folding
    好像就是好几个vp树组合起来
    """
    def __init__(self, dist_fn, min_tree_size=4):
        """
        :param dist_fn: Metric distance function used for vp-trees
        :param min_tree_size: Minimum number of nodes to form a tree (extra nodes are stored in a pool until the number is reached)

        :param dist_fn: 用于VP树的度量距离函数
        :param min_tree_size: 构建一棵树所需的最小节点数（多余的节点会被存储在一个池中，直到达到最小节点数才会形成新的树）
        """

        self.dist_fn = dist_fn
        self.trees = []#组合好几个树
        self.pool = []
        self.min_tree_size = min_tree_size

    def insert(self, item):
        """
        Insert item into dynamic vp tree by first adding to pool, and then building a tree from the pool if min size reached
        Then merge trees of equal sizes so that there are at most log(log (n)) trees, with the largest tree having roughly n/2 nodes

        将项目插入动态VP树，首先将其添加到池中，如果达到了最小大小，则从池中构建树。
        然后合并大小相等的树，使得最多有log（log（n））棵树，最大的树大约有n/2个节点。
        """
        self.pool.append(item)
        if len(self.pool) == self.min_tree_size:
            self.trees.append(_ExtendedVPTree(self.pool, self.dist_fn))
            self.pool = []
        while len(self.trees) > 1 and self.trees[-1].size == self.trees[-2].size:
            #tree[-1],tree[-2]代表最后两个元素
            a = self.trees.pop()
            b = self.trees.pop()
            self.trees.append(_ExtendedVPTree(a.points + b.points, self.dist_fn))
            #合并树

    def nearest(self, query):
        """
        query查询
        Return node nearest to query by finding nearest node in each tree and returning the global minimum (including nodes in pool)
        通过找到每棵树中距离查询最近的节点，返回最接近查询的节点（包括池中的节点）。
        """
        nearest_trees = list(map(lambda t: t.get_nearest_neighbor(query), self.trees))
        """
        get_nearest_neighbor是自带的函数，返回trees中的每个vptree，离query最近的点
        
        
        在 Python 中，map() 是一种内置函数，用于对可迭代对象中的每个元素应用一个函数，并将结果作为迭代器返回。
        lambda 表达式的优点是可以在需要函数对象的地方直接使用它，而不需要事先定义一个具名函数。
        例如，在 map() 函数中可以使用 lambda 表达式快速地对列表中的每个元素进行操作：
        
        具体地，该行代码使用了Python内置的map()函数和lambda表达式，其作用是将get_nearest_neighbor(query)方法应用到self.trees中的每一个元素t上，并将返回值组成一个列表返回给nearest_trees变量。
        """
        distances_pool = list(zip(map(lambda x: self.dist_fn(x, query), self.pool), self.pool))
        # 备选池子里的也算一下
        best = None
        best_cost = np.inf
        for cost, near in nearest_trees + distances_pool:
            if cost <= best_cost:
                best = near
                best_cost = cost
        return best

    def neighbourhood(self, query, radius):
        """
        Return all nodes within distance radius of the given query, by collating neighbourhoods for each internal tree (and pool)
        通过收集每个内部树（和池中的节点）的邻域，返回给定查询半径内的所有节点。
        """
        tree_neighbourhood = lambda tree: list(map(lambda x: x[1], tree.get_all_in_range(query, radius)))
        '''
        lambda arguments(输入): expression
        定义一个 lambda 函数 tree_neighbourhood，
        它将输入一个树对象 tree，
        返回该树中与给定状态 query 距离在 radius 范围内的所有节点（使用 get_all_in_range 方法实现）。
        get_all_in_range是vptree自带的，tree里有好几个vptree,为什么用x[1]？
        '''
        neighbourhood_trees = list(itertools.chain.from_iterable(map(tree_neighbourhood, self.trees)))
        '''
        对 self.trees 中的每棵树都应用 tree_neighbourhood 函数，
        并使用 itertools.chain.from_iterable 将每个树的搜索结果合并成一个列表（neighbourhood_trees）。
        '''
        return neighbourhood_trees + list(filter(lambda x: self.dist_fn(x, query) < radius, self.pool))
